package class3;

import common.ListNode;
import common.ListNodeUtils;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/remove-duplicate-node-lcci/description/?envType=problem-list-v2&envId=linked-list
 * 移除重复节点
 * 解题思路：
 * 1.使用set集合判断是否已经有该节点
 */
public class Code19_RemoveDuplicateNodes {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1, 2, 3, 3, 2, 1);
        ListNode listNode = removeDuplicateNodes(head);
        ListNodeUtils.print(listNode);
    }

    public static ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        ListNode last = null;
        // 遍历链表
        while (cur != null) {
            if (set.contains(cur.val)) {
                last.next = cur.next;// 当集合中有该值时，跳过重复节点
            } else {
                //当值不存在时，last向下指
                set.add(cur.val);
                last = cur;  // 只有不删除时才更新 last
            }
            cur = cur.next;
        }
        return head;
    }
}
